1. Field of Invention
This invention relates generally to a system and method for classifying input patterns into one of two classes, a class-of-interest or a class-other, utilizing an Adaptive Fisher's Linear Discriminant method capable of estimating an optimal linear decision boundary for discriminating between the two classes, when training samples are provided a priori only for the class-of-interest. The system and method eliminates the requirement for any a priori knowledge of the other classes in the data set to be classified.
2. Prior Art
Pattern recognition is used in a variety of engineering and scientific areas. Interest in the area of pattern recognition has been renewed recently due to emerging new applications which are not only challenging but also computationally more demanding [A. K. Jain, R. W. Duin, and J. Mao, “Statistical Pattern Recognition: A Review”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, January 2000, pp. 4-37]. These applications include identification of people based on biometrics, classification of remotely sensed images (thematic mapping, crop inventorying), document classification (searching for text documents), financial forecasting, organization and retrieval of multimedia data bases, and recognition of objects-of-interest in images (real-time identification of high valued military targets in imagery, and screening of x-rays and MRI's for medical conditions).
Of particular interest since 9/11 is biometrics—identification of people based on distinctive personal traits (such as facial characteristics, fingerprints, speech patterns) and screening/monitoring people in public places for persons of interest [A. K. Jain, “Biometrics: A Grand Challenge”, Proceeding of the 17th International Conference on Pattern Recognition, (ICPR'04)]. In the USA Patriot Act and the Enhanced Border Security and Visa Entry Reform Act of 2002, the U.S. Congress mandated the use of biometrics in U.S. visas [NIST report to the United States Congress, “Summary of NIST Standards for Biometric Accuracy, Tamper Resistance, and Interoperability.” Available at ftp://sequoyah.nist.gov/pub/nist_internal_reports/NISTAPP_Nov02.pdf, November 2002.]. This law requires that Embassies and Consulates abroad must now issue to international visitors “only machine-readable, tamper-resistant visas and other travel and entry documents that use biometric identifiers”. Congress also mandated the development of technology that uses these biometric identifiers to positively identify person entering the United States.
Most of the literature on pattern recognition is restricted to fully supervised pattern recognition applications where training samples are available which completely characterize all of the classes (or objects) to be recognized in a data set. Using these training samples, optimal discriminant boundaries can be derived which provide minimum error in recognizing these known classes (or objects) in a data set.
However, in many important pattern recognition applications, training samples are only available for the classes-of-interest (or objects-of-interest). The distribution of the other classes may be; 1) unknown, 2) may have changed 3) may be inaccurate due to insufficient numbers of samples used to estimate the distribution of the other classes, or 4) the cost of obtaining labeled training samples may be expensive are difficult to obtain. Often one is only interested in a single class or a small number of classes.
The simplest technique for handling the problem of unknown classes consists of thresholding based on a measure of similarity of a measurement to the class-of-interest [B. Jeon and D. A. Landgrebe, “Partially Supervised Classification With Optimal Significance Testing,” Geoscience and Remote Sensing Symposium, 1993, pp. 1370-1372]. If the similarity measure (a statistical probability) is lower than some threshold, the sample is assumed to belong to an unknown class; otherwise, it is assigned to the class-of-interest. Even if an optimal threshold is selected, this procedure does not ensure minimum probability of error in classification.
The Fisher's linear discriminant procedure is used in many pattern recognition applications to discriminate between two classes. It provides accurate classifications and is computationally efficient since it uses a linear decision boundary. However the standard Fisher's linear discrimination procedure requires that training samples be available for the both classes [R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis, New York: John Wiley & Sons, 1973, pp. 115-121].
This invention defines an Adaptive Fisher's Linear Discriminant method for discriminating between two classes, a class-of-interest and a class-other, when training samples are provided a priori only for the class-of-interest. The system and method is capable of estimating an optimal Fisher's linear decision boundary for discriminating between the two without any a priori knowledge of the other classes in the data set to be classified.
The system and method is capable of extracting statistical information corresponding to the “other classes” from the data set to be classified, without recourse to the a priori knowledge normally provided by training samples from the other classes. The system and method provides classification accuracies equivalent to robust and powerful discriminating capability provided by fully supervised classification approaches.
Examples where this type of capability would be very beneficial can be found in Home Land Security, face recognition, remote sensing, and target recognition applications.
Home Land Security has a need for security screening and surveillance in public spaces to determine the presents of a person on a watch-list using facial biometrics [A. K. Jain, “Biometrics: A Grand Challenge”, Proceeding of the 17th International Conference on Pattern Recognition, (ICPR'04)]. The screening watch-list typically consists of a few hundred persons. Normally no a priori knowledge is available of the identities on the other persons observed in the public space that might be mis-identified with the people on the watch-list.
In remote sensing applications, ground truth maps providing a priori information on all land cover typologies in an image, do not really describe all the types of land cover types in the image being classified [P. Mantero, “Partially supervised classification of remote sensing images using SVM-based probability density estimation”, IEEE Transactions on Geoscience and Remote Sensing, vol. 43, no. 3, March 2005, pp. 559-570]. In addition, one is often interested in identifying picture elements (pixels) belonging to only one or a small number of classes. Generation of a complete training set for all the land cover types in an image is time-consuming, difficult, and expensive.
Target recognition applications [B. Eckstein, “Evaluating the Benefits of assisted Target Recognition”, Proceeding of the 30th Applied Imagery Pattern recognition Workshop (AIPR″01)] [S. Rizvi, “Fusion Techniques for Automatic Target Recognition”, Proceedings of the 32nd Applied Imagery Pattern Recognition Workshop (AIPR'03)] often involve recognition of high valued mobile military targets such as tanks in imagery data collected in real time. Often no a priori knowledge is available of the other objects in the image which might be confused with a tank—such as decoys (anything that mimics a target but is not a real target), background clutter, man-made structures, and civilian vehicles.